package week09

// 37. 解数独
// https://leetcode-cn.com/problems/sudoku-solver/

func solveSudoku(board [][]byte)  {
	var n = len(board)
	var row = makeRecord(n)
	var col = makeRecord(n)
	var grid = makeRecord(n)

	for i := range board {
		for j := range board[i] {
			if board[i][j] != '.' {
				index := board[i][j] - '0'
				row[i][index], col[j][index], grid[i/3*3+j/3][index] = true, true, true
			}
		}
	}

	dfs(board, row, col, grid)
}

func dfs(board [][]byte, row, col, grid [][]bool) bool {
	i, j := findSpace(board)
	if i == -1 {
		return true
	}

	for k := 1; k <= 9; k++ {
		gridId := i/3*3+j/3
		rv, cv, gv := row[i][k], col[j][k], grid[gridId][k]
		if rv || cv || gv {
			continue
		}
		board[i][j] = byte(k) + '0'
		row[i][k], col[j][k], grid[gridId][k] = true, true, true
		if dfs(board, row, col, grid) {
			return true
		}
		board[i][j] = '.'
		row[i][k], col[j][k], grid[gridId][k] = rv, cv, gv
	}
	return false
}

func findSpace(board [][]byte) (int, int) {
	for i := range board {
		for j := range board[i] {
			if board[i][j] == '.' {
				return i, j
			}
		}
	}
	return -1, -1
}

func makeRecord(n int) [][]bool {
	var record = make([][]bool, n)
	for i := range record {
		record[i] = make([]bool, 10)
	}
	return record
}